|
Mobile ad-hoc networks (MANETs) are used in situations where
networks need to be deployed immediately but no network
infrastructure is available. If MANET nodes have sensing
capabilities, they can capture and communicate the state of their
surroundings, including environmental conditions or objects in their
proximity. If the sensed state information is propagated to a
database to build a consistent model of the real world, a variety of
promising context aware applications becomes possible.
The models and concepts proposed in this dissertation can be applied
to cooperatively maintain a model of the state of physical world
objects on devices in MANETs. State information may be updated by
independent observers either sequentially or concurrently.
Applications that read the state of any object from the model
multiple times can rely on the guarantee that every successive read
operation will read either the same state information or newer state
information that has been reported by an observer after the
previously read information.
The first contribution of this dissertation formalizes these
requirements and defines a novel consistency model called
update-linearizability. Secondly, it introduces a new class of data
replication algorithms that provably guarantees
update-linearizability in MANETs without using synchronized clocks
on any pair of nodes in the system. The presented algorithms allow
executing read and write operations at any time, which provides high
availability of data. These properties are even maintained in
networks that are temporarily partitioned and where nodes are highly
mobile. Finally the dissertation provides a proof that all replicas
held in the system eventually converge towards the most recent state
information of the physical world objects which they represent.
|